package 力扣_数学思维题;

import java.util.HashMap;
import java.util.Map;

/**560.和为K的子数组
 * @author zx
 * @create 2022-04-27 16:29
 * 这个思路不是很容易想到，需要多做一些类似的问题慢慢培养感觉。
 * 同类问题有：
 * 「力扣」第 1 题：两数之和
 * 「力扣」第 1248 题： 统计「优美子数组」
 * 「力扣」第 454 题：四数相加 II
 */
public class Num560 {
    /**
     解释一开始 map.put(0, 1) 的意义
     想一想算法的意思：
     计算完包括了当前数前缀和以后，我们去查一查在当前数之前，有多少个前缀和等于 preSum - k 呢？
     这是因为满足 preSum - (preSum - k) == k 的区间的个数是我们所关心的。
     对于一开始的情况,下标0之前没有元素,可以认为前缀和为0,个数为1个,因此map.put(0, 1);这一点是必要且合理的.
     具体的例子是：nums = [3,...], k = 3，和 nums = [1, 1, 1,...], k = 3。
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        // key：前缀和,value：key对应的前缀和的个数
        Map<Integer,Integer> map = new HashMap<>();
        // 对于下标为 0 的元素,前缀和为 0,个数为 1
        map.put(0,1);
        int preSum = 0;
        int res = 0;
        for(int i = 0;i < nums.length;i++){
            preSum += nums[i];
            if(map.containsKey(preSum - k)){
                res += map.get(preSum - k);
            }
            if(map.containsKey(preSum)){
                map.put(preSum,map.get(preSum) + 1);
            }else{
                map.put(preSum,1);
            }
        }
        return res;
    }

    /**
     * @return 暴力解法
     */
    public int subarraySum2(int[] nums, int k) {
        int res = 0;
        for(int i = 0;i < nums.length;i++){
            int sum = 0;
            for(int j = i;j < nums.length;j++){
                sum += nums[j];
                if(sum == k){
                    res++;
                }
            }
        }
        return res;
    }
}
